#include <iostream>
#include <queue>

using namespace std;

class WordDictionary {
private:
    struct word_node {
        bool end = false;
        word_node* dict[26] = {nullptr};
    };
    word_node word_head;
public:
    /** Initialize your data structure here. */
    WordDictionary() {}

    /** Adds a word into the data structure. */
    void addWord(string word) {
        word_node* node = &word_head;
        for (char item : word) {
            if (node->dict[item - 'a'] == nullptr) {
                node->dict[item - 'a'] = new word_node;
            }
            node = node->dict[item - 'a'];
        }
        node->end = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        queue<word_node*> queue;
        queue.push(&word_head);
        for (char item : word) {
            if (item == '.') {
                for (int i = 0, len = queue.size(); i < len; i++) {
                    word_node* node = queue.front();
                    queue.pop();
                    for (int i = 0; i < 26; i++) {
                        if (node->dict[i] != nullptr) {
                            queue.push(node->dict[i]);
                        }
                    }
                }
                if (queue.size() == 0) {
                    return false;
                }
            } else {
                for (int i = 0, len = queue.size(); i < len; i++) {
                    word_node* node = queue.front();
                    queue.pop();
                    if (node->dict[item - 'a'] != nullptr) {
                        queue.push(node->dict[item - 'a']);
                    }
                }
                if (queue.size() == 0) {
                    return false;
                }
            }
        }
        while (queue.size() > 0) {
            word_node* node = queue.front();
            queue.pop();
            if (node->end) {
                return true;
            }
        }
        return false;
    }
};
